#include <iostream>
#include <cstdlib> // for rand
#include <ctime>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

// create a function object
// this is not a function but looks like one.
// it differs from a function in that data 
// is persistant.
struct sumk{
	int total;
	sumk():total(0){}// constructor
	void operator()(int i){total+=i;}//overload (x) operator
};

void main(){

	// declare a container to hold ints
   vector<int> v;
    
   // load the container with random #'s
   srand(time(0));
   for(int i = 0; i < 5; i++)
	   v.push_back(rand()%10+1);

   // show original
   cout <<"Original Data"<<endl;

   // use an iterator to traverse container
   vector<int>::iterator it;// declare iterator variable
   for(it = v.begin(); it != v.end(); it++)// must use !=
      cout << *it << endl;  // "dereference" the iterator

   // use the sort algorithm
   sort(v.begin(), v.end());

   // do an O(log(n)) search
   cout << "search for 1-10 yields " << endl;
   for(int i = 0; i < 10; i++)
   cout << binary_search(v.begin(), v.end(), i+1);
   cout << endl;

   // show results
   cout <<"Sorted Data"<<endl;

   // use an ostream iterator instead of a for loop
   ostream_iterator<int> out(cout, "\n");
   copy(v.begin(), v.end(), out);

   // backwards the wrong way
   cout << "incorrect print reverse sorted data" << endl;
   copy(v.begin(), v.end(), out);

   // backwards the correct way
   cout << "correct print reverse sorted data" << endl;
   vector<int>::reverse_iterator ri;
   for(ri = v.rbegin(); ri != v.rend(); ri++)
	   cout << *ri << endl;

   // use random shuffle algorithm
   cout <<"After shuffle"<<endl;
   random_shuffle(v.begin(), v.end());
   copy(v.begin(), v.end(), out);



   sumk sk;
   sk(3); sk(4); sk(-1);
   cout << "sumk result: " << endl;
   cout << sk.total << endl;

   // report on sum of vector ints
   cout << (for_each(v.begin(), v.end(), sumk())).total << endl;

   // show similarity between list and vector
   list<int> k;
   for(int i = 0; i < 5; i++)
	   k.push_back(rand()%10+1);
   cout << "list data" << endl;
   list<int>::iterator ik;
   copy(k.begin(), k.end(), out);

   // report on sum of list ints
   cout << "sum of list ints " << endl;
   cout << (for_each(k.begin(), k.end(), sumk())).total << endl;

   // this notation is exceptional in the STL
   k.sort();

   // show result of sort
   cout<<"sorted linked list"<<endl;
   for(ik = k.begin(); ik != k.end(); ik++)
      cout << *ik << endl;  


 

}